Computer graphics techniques typically involve manipulating computer-generated objects. Many techniques have evolved to assist in object manipulation, one of which typically represents or approximates an object and, in particular, approximates the surface of an object as collections of other smaller objects like polygons, e.g. triangles. That is, objects, some of which might have fairly complex surface characteristics, can be represented as collections of triangles that collectively represent or approximate the surface characteristics of the object. When object manipulation takes place, the manipulation operations are performed relative to the smaller shapes that approximate the surface of the object.
One technique that is used to manipulate objects is ray intersection. Ray intersection techniques can be used in a number of different scenarios that include image rendering, object selection, and surface interrogation (i.e. surface querying).
In image rendering, a ray can be directed from a visual point toward a picture element on a screen. Each object that is hit, or intersected, by the ray is set as an object to be drawn on the picture element to which the color of the object is allocated. This method of color processing the object can render effects of optical attributes, such as the reflection or the refraction of the object on the color of the object drawn on the screen by using the colors of the reflected ray from another object or the refracted ray through another object. Therefore, this method can precisely express reflexes by the reflection or the refraction of other objects surrounding the intersected object.
Object selection involves operations where a user wants to directly manipulate a rendered image. For example, there may be a rendering of a scene that has particular objects in it. A user can click an object or a particular point on an object with a mouse, grab it, move it, and manipulate it. In this instance, the mouse click essentially casts a ray into the scene and determines the first object portion to be struck or intersected by the ray. Subsequent processing can take place based upon which objects are intersected by the ray.
Surface interrogation can involve an object moving through a rendered scene. In such applications, ray-intersection may be used to enable a determination as to which objects the moving object is about to collide with.
A majority of the processing that takes place in connection with ray-intersection concerns searching for an object that is intersected by a cast ray. Where, as here, the surface of objects are approximated by a plurality of shapes, e.g. triangles, conventional searching takes place by determining whether or not each and every shape that constitutes the approximated surface of an object is intercepted by the cast ray. For example, if the surface of an object is approximated by 6500 triangles, conventional searching algorithms test a first triangle to determine whether the cast ray intercepts it. If the first triangle is not intercepted by the cast ray, then the next triangle is tested and so on. Needless to say, processing each of the shapes used to approximate the surface of an object, while effective, is not the most optimal approach to the problem. Additional background information can be found in the following U.S. Pat. Nos.: 5,594,844, 5,933,146, 5,313,568, 5,091,960, and 5,138,699.
Accordingly, this invention arose out of concerns associated with improving the apparatus and methods that are used in connection with computer graphics. In particular, the invention arose out of concerns associated with improving object-intersection processing techniques.